package 剑指offer;

import java.util.Stack;



/** 

* @author ：soulstones
* @version ：2019年9月30日 下午7:31:23 
* @Description：
* 

*/
public class $5用两个栈实现队列 {
	
	
	//队列的特性是“先进先出”，栈的特点是“先进后出”
	
	/*
	 * 例如，有一个队列，进入顺序为 a,b,c,出队顺序是a，b,c
	 * 但是在一个队列当中是 ，入：a,b,c     出：c,b,a
	 * 。现在借助两个栈可以实现一个队列
	 * stack1 :入队  a,b,c   出队：c,b，a
	 * stack2:完全可以将stack1中出栈的元素作为入栈元素进行入栈，待stack1.pop()中的全部元素出栈
	 * 随即按照这个顺序入栈stack2.这样一来，stack的入栈顺序weic，b,a,那他的出栈顺序就是a,b,c啦
	 * 
	 * 这样一来，stack1进行入栈再出栈到stack2,stack2再出栈就是一个简单的队列了
	 * 
	 * 自己最先考虑的暴力思想：
	 *   在stack1，stack2都为空时，第一个元素入栈到stack1,在进行
	 *   第二个元素入栈前，将stack1的栈底元素弹出，并入栈到stack2中，这时将第二个元素入栈到stack1的栈底了
	 *   最后再将stack2中的元素（其实就是第一个入队的元素）出栈再入栈到stack1中。
	 *   这样一来，每当入队一个元素，都要进行多次重复的倒栈操作，效率不高
	 */
		Stack<Integer> stack1 = new Stack<>();
		Stack<Integer> stack2 = new Stack<>();
		
	public void push(int node) {
		stack1.push(node);          // stack1只管作为入栈（入队）操作
	}

	
	public int pop() {
		
		if(stack1.empty()&&stack2.empty()) {           
			throw new RuntimeException("Queue is Empty");
		}
		
		if(stack2.empty()) {              
			while(!stack1.empty())              //当需要出队时，将stack1中的全部元素依次出栈，并入栈到stack2中，
				stack2.push(stack1.pop());    //这样一来，stack2中的元素顺序就是典型的出队序列了。
		}
		return stack2.pop();
	}
	
	public static void main(String[] args) {
		
	}
	
}
